The present invention relates to de-interlacing image buffers in digital image capture devices, and more particularly to de-interlacing image buffers in devices utilizing image capture sensors, such as CCDs and CMOS sensors that have interlaced output data.
The fundamental purpose of a digital imaging device is to convert a view of the real world to a 2-D array of digital pixels. Photons emitted by objects in a scene as well as photons reflected by objects in the scene are focused onto an image sensor by an optical system. The optical system produces a 2-D image of the (usually) 3-D scene and the optics determines the relative focus, depth of field, maximum resolution, etc. of the 2-D image.
The 2-D image incident on the sensor is then converted from photons to electrical charge by the sensor. The sensor is composed of a rectangular grid of photo-sensitive sites, called pixels, and each row of pixels is referred to as a scan line. At each pixel, a charge is accumulated when light falls on that area. In this way, the sensor builds up an array of charges which are a close approximation of the relative brightness of the 2-D image. Typical sensor devices are CCD (charge coupled device) or CMOS (complimentary metal oxide) technology, and have millions of pixels.
Once the sensor has been exposed to the 2-D image for some period of time, the resulting pixel charges must be read from the device. The output signal is typically a series of analog voltages produced sequentially for each pixel location. This type of signal is not readily manipulated by a digital computer. Conversion from analog voltages to digital numbers is accomplished using an ADC (analog to digital converter) which produces an n-bit number given a voltage input, where n is typically 8, 10, or 12 for digital cameras.
A hardware subsystem of the digital computer is used to quickly transfer each digital number produced by the ADC to a buffer within the computer""s memory. This subsystem is called a DMA (direct memory access) engine because it directly accesses (writes the image data) memory without the CPU (central processing unit) being utilized. This allows the CPU to perform other operations in parallel, thus making better use of system resources.
The order of pixel read-out from the sensor to the ADC may be either interlaced or progressive scan. In both cases, entire scan lines of pixels are sequentially output as voltages starting at one end of the scan line and proceeding to the other end. In progressive scan devices, the order of read-out of the scan lines is also sequential, starting at either the top or the bottom of the sensor and progressing to the bottom or top, respectively. For example, in a small 4-scan line progressive scan device, the scan lines might be read from top to bottom: 0, 1, 2, 3; or from bottom to top: 3, 2, 1, 0.
By contrast, in an interlaced scan device the order of read-out of the scan lines is not sequential, but rather, first all of the even scan lines are read out in order followed by all of the odd scan lines. For example, a small 4-scan line interlaced scan device might be read from top to bottom: 0, 2, 1, 3; or from bottom to top: 2, 0, 3, 1. FIG. 1 is a block diagram illustrating the contents of a conventional 1208 scan line image buffer after an interlaced transfer.
For purposes of manipulating image data in a digital computer, it is preferred to have the scan lines stored in the buffer memory in a progressive scan order. In some systems, the interlaced scan lines can be easily re-ordered as they are being read-out from the ADC. The actual transfer of data from the ADC to the computer""s digital memory is done using DMA (direct memory access). Some processors have DMA engines that are capable of performing this re-ordering of scan lines automatically. This is the most efficient method of de-interlacing the image data since it requires no extra memory or computer processing time (beyond the actual DMA transfer time).
In cases where the DMA engine is not capable of de-interlacing the image scan lines, they must be de-interlaced after they have been transferred to memory using a software algorithm running in the computer. This operation will utilize system resources including, extra memory, CPU processing time, and bus bandwidth.
The most straightforward algorithm for de-interlacing the image scan lines requires a second image buffer in memory which is the same size as the interlaced image buffer. Each scan line is then read from the interlaced buffer and written into the desired scan line position in the resulting progressive buffer.
This method has two disadvantages. First, it requires a potentially large second image buffer. In a digital imaging system, memory is a very limited resource so requiring an entire image buffer is a severe penalty. Second, since the algorithm reads scan lines from one buffer and writes them into another buffer, the memory cache is less likely to help with reducing bus bandwidth used during de-interlacing. This will cause system throughput to suffer. In short, large amounts of memory are unavailable for use elsewhere in the device (e.g. for capturing another image) while the de-interlace algorithm is running.
Accordingly, what is needed is more efficient method for de-interlacing an image buffer. The present invention addresses such a need.
The present invention provides a method and apparatus for de-interlacing a buffer of image data, wherein scan lines from an image sensor have been transferred to the buffer and stored in a group of even scan lines and a group of odd scan lines. The method for de-interlacing the buffer includes providing a first table to indicate current storage locations of each scan line in the buffer and providing a second table to indicate which scan line is currently stored in each storage location. The first table and a temporary line buffer are then used iteratively swap pairs of scan lines that are stored out of numerical order in the buffer, such that after a swap, one of the scan line in the pair is stored in numerical order in the buffer. After each swap, the first table is updated using the second table, and then second table is updated, such that the first and second tables reflect a change of storage locations for the scan lines.
According to the method and apparatus disclosed herein, the image buffer is de-interlaced in place without the need for an entire duplicate buffer, which save memory and decreases memory transfers, thereby increasing overall system performance.